package 力扣.二分.三步切分法;

public class 寻找旋转排序数组中的最小值II_154 {
    /**
     * 本题是153题的进阶版，存在重复的元素
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int N = nums.length;
        int l = 0,r = N - 1;
        while (l < r){//保证区间里面至少还有两个元素，这样才有可比性
            int m = l + ((r - l) >> 1);
            if (nums[m] > nums[r]){
                l = m + 1;
            }else if (nums[m] < nums[r]){
                r = m;
            }else {//nums[m] == nums[r] 如[1,1,0,1]
                r--;//此时r肯定不是最小值，扔掉
            }
        }
        return nums[l];
    }

    public int findMin2(int[] nums) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int N = nums.length;
        int l = 0, r = N -1;
        while (l < r){
            int m = l + ((r - l) >> 1);
            if (nums[m] > nums[r]){
                l = m + 1;
            }else if (nums[m] == nums[r]){
                r--;
            }else {
                r = m;
            }
        }
        return nums[l];
    }

    public int findMin3(int[] nums) {
         if(nums == null || nums.length == 0){
             return 0;
         }
         final int N = nums.length;
         int l = 0,r = N -1;
         while (l < r){
             int m = l + ((r- l) >> 1);
             if (nums[m] > nums[r]){
                 l = m + 1;
             }else if (nums[m] == nums[r]){
                 r--;
             }else {
                 r = m;
             }
         }
         return nums[l];
    }




}
